<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Z Algorithm Z values</title>
        <style>
</style>
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.10.2/dist/katex.min.css" integrity="sha384-yFRtMMDnQtDRO8rLpMIKrtPCD5jdktao2TV19YiZYWMDkUR5GQZR/NOVTdquEx1j" crossorigin="anonymous">
<link href="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.css" rel="stylesheet" type="text/css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        <script src="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.js"></script>
        
    </head>
    <body class="vscode-light">
        <h1 id="z-algorithm-z-values">Z Algorithm Z values</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=CpZh4eF8QBw&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de">https://www.youtube.com/watch?v=CpZh4eF8QBw&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/string/ZAlgorithm.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/string/ZAlgorithm.java</a></li>
</ul>
<p>字符串查找算法, 复杂度 O(m+n)
(1) 构建新的字符串 pattern + &quot;$&quot; + text
(2) 按照前缀查找方法</p>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.string;

<span class="hljs-keyword">import</span> java.util.ArrayList;
<span class="hljs-keyword">import</span> java.util.List;

<span class="hljs-comment">/**
 * Date 10/31/2015
 * <span class="hljs-doctag">@author</span> Tushar Roy
 *
 * Z algorithm to pattern matching
 *
 * Time complexity - O(n + m)
 * Space complexity - O(n + m)
 *
 * http://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
 * http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ZAlgorithm</span> </span>{

    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span>[] calculateZ(<span class="hljs-keyword">char</span> input[]) {
        <span class="hljs-keyword">int</span> Z[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[input.length];
        <span class="hljs-keyword">int</span> left = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> right = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>; k &lt; input.length; k++) {
            <span class="hljs-keyword">if</span>(k &gt; right) {
                left = right = k;
                <span class="hljs-keyword">while</span>(right &lt; input.length &amp;&amp; input[right] == input[right - left]) {
                    right++;
                }
                Z[k] = right - left;
                right--;
            } <span class="hljs-keyword">else</span> {
                <span class="hljs-comment">//we are operating inside box</span>
                <span class="hljs-keyword">int</span> k1 = k - left;
                <span class="hljs-comment">//if value does not stretches till right bound then just copy it.</span>
                <span class="hljs-keyword">if</span>(Z[k1] &lt; right - k + <span class="hljs-number">1</span>) {
                    Z[k] = Z[k1];
                } <span class="hljs-keyword">else</span> { <span class="hljs-comment">//otherwise try to see if there are more matches.</span>
                    left = k;
                    <span class="hljs-keyword">while</span>(right &lt; input.length &amp;&amp; input[right] == input[right - left]) {
                        right++;
                    }
                    Z[k] = right - left;
                    right--;
                }
            }
        }
        <span class="hljs-keyword">return</span> Z;
    }

    <span class="hljs-comment">/**
     * Returns list of all indices where pattern is found in text.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> List&lt;Integer&gt; <span class="hljs-title">matchPattern</span><span class="hljs-params">(<span class="hljs-keyword">char</span> text[], <span class="hljs-keyword">char</span> pattern[])</span> </span>{
        <span class="hljs-keyword">char</span> newString[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">char</span>[text.length + pattern.length + <span class="hljs-number">1</span>];
        <span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">char</span> ch : pattern) {
            newString[i] = ch;
            i++;
        }
        newString[i] = <span class="hljs-string">'$'</span>;
        i++;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">char</span> ch : text) {
            newString[i] = ch;
            i++;
        }
        List&lt;Integer&gt; result = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
        <span class="hljs-keyword">int</span> Z[] = calculateZ(newString);

        <span class="hljs-keyword">for</span>(i = <span class="hljs-number">0</span>; i &lt; Z.length ; i++) {
            <span class="hljs-keyword">if</span>(Z[i] == pattern.length) {
                result.add(i - pattern.length - <span class="hljs-number">1</span>);
            }
        }
        <span class="hljs-keyword">return</span> result;
    }

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span> </span>{
        String text = <span class="hljs-string">"aaabcxyzaaaabczaaczabbaaaaaabc"</span>;
        String pattern = <span class="hljs-string">"aaabc"</span>;
        ZAlgorithm zAlgorithm = <span class="hljs-keyword">new</span> ZAlgorithm();
        List&lt;Integer&gt; result = zAlgorithm.matchPattern(text.toCharArray(), pattern.toCharArray());
        result.forEach(System.out::println);
    }


}
</div></code></pre>

    </body>
    </html>